package ljl.alg.jianzhioffer.round2;

import commons.ListNode;

public class _24_reverse_list {
    
    /*
    * 写了几百遍了
    * */
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode h = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return h;
    }
    
    public ListNode reverseList2(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    
    /**
     * 万万没想到，我又碰到了不会的地方，
     * 还是玩不转！
     *
     * 总感觉这个是正经的递归！和上面那个比起来
     * */
    public ListNode reverseList3(ListNode head) {
        return recur(head, null);
    }
    
    ListNode recur(ListNode cur, ListNode prev) {
        if (cur == null) return prev;
        ListNode res = recur(cur.next, cur);
        cur.next = prev;
        return res;
    }
}
